#ifndef _HEAP_
#define _HEAP_

#include <iostream>

#define DEFAULT_MAX 100

#define leftChild(parentIndex)  ((parentIndex << 1) + 1)
#define rightChild(parentIndex) ((parentIndex << 1) + 2)
#define parent(index) 			(index >> 1)
#define hasLeft(index) 	  		(leftChild(index) < (int)heapCount)
#define hasRight(index)   		(rightChild(index) < (int)heapCount)
#define isLeaf(index)			!(hasLeft(index) || hasRight(index))

using namespace std;

template<typename T, int (*C)(T, T)> class Heap {

private:
	T* heapArray;
	T* originalHeapArray;
	unsigned int heapCount;
	unsigned int heapSize;
	unsigned int heapMemory;
	unsigned int freezedCount;
	bool isHeap;

	// Swapea el contenido de a por el de b y viceversa
	static void swap(T *a, T *b) {
		if (a != b) {
			T c = *a;
			*a = *b;
			*b = c;
		}
	}

	// Reconstruye elheap cuando se produce un cambio en el nodo i y el resto de la estructura CUMPLE AL CONDICION DE HEAP.

	void rebuildHeap(int i) {

		int l = leftChild(i);
		int r = rightChild(i);
		int next = i;

		if (isLeaf(i))
			return;

		//Alguno no cumple la condicion de heap?
		if (hasLeft(i) && (C(heapArray[l], heapArray[i]) < 0))
			next = l;

		if (hasRight(i) && (C(heapArray[r], heapArray[next]) < 0))
			next = r;

		//Reconstruime el heap si alguno no cumplia la condicion de heap
		if (next != i) {
			swap(&heapArray[i], &heapArray[next]);
			rebuildHeap(next);
		}

	}

	// Llamada recursiva del heapify. Hace recorrido en profundidad.

	void heapify(int i) {

		int l = leftChild(i);
		int r = rightChild(i);
		int next = i;

		if (isLeaf(i))
			return;

		//Traemos el menor de la izquierda y el menor de la derecha. Esto es porque nada garaniza que los hijos cumplan con la condicion de heap
		heapify(l);
		heapify(r);

		//Alguno no cumple la condicion de heap?
		if (hasLeft(i) && (C(heapArray[l], heapArray[i]) < 0))
			next = l;

		if (hasRight(i) && (C(heapArray[r], heapArray[next]) < 0))
			next = r;

		//Reconstruime el heap si alguno no cumplia la condicion de heap
		if (next != i) {
			swap(&heapArray[i], &heapArray[next]);
			rebuildHeap(next);
		}

	}

protected:

	T& operator[](int index) {
		//hacer validacion del index
		return this->heapArray[index];
	}

public:
	Heap() {
		originalHeapArray = heapArray = new T[DEFAULT_MAX];
		heapCount = 0;
		isHeap = false;
		heapMemory = heapSize = DEFAULT_MAX;
		freezedCount = 0;
	}
	;

	Heap(unsigned int max) {
		originalHeapArray = heapArray = new T[max];
		heapMemory = heapSize = max;
		heapCount = 0;
		isHeap = false;
		freezedCount = 0;
	}
	;

	~Heap() {
		delete[] originalHeapArray;
	}
	;

	// Un print con formato. Mayormente para debugging
	friend ostream& operator<<(ostream &out, Heap &heap) {

		for (int array_index = 0; array_index < heap.heapCount; array_index++)
			out << heap[array_index] << " ";

		return out;

	}

	// La primitiva de Load (carga) no reconstruye el heap cuando se usa. Es mas que nada para la carga inicial del heap

	bool loadItem(T item) {
		if (heapCount >= heapSize)
			return false;

		heapArray[heapCount] = item;
		heapCount++;

		return true;
	}

	// Transforma el array en un heap

	void heapify() {
		heapify(0);
		isHeap = true;
	}
	;

	// La primitiva de add (Alta) reconstruye el heap cuando se usa.

	bool pushItem(T item) {
		if (heapCount >= heapSize)
			return false;

		heapArray[heapCount] = item;
		heapCount++;

		heapify();

		return true;
	}

	// Devuelve el menor de los elementos y reconstruye el heap.

	T popItem() {

		if (heapCount == 0)
			throw new string("Could not popItem: Heap is empty");

		T temp = heapArray[0];

		heapArray[0] = heapArray[heapCount - 1];
		heapCount--;

		rebuildHeap(0);
		return temp;
	}

	// Devuelve el menor de los elementos y reconstruye el heap.

	T pushAndPopItem(T item) {
		T temp = heapArray[0];

		heapArray[0] = item;

		rebuildHeap(0);

		return temp;
	}

	unsigned int size() {
		return heapSize;
	}

	unsigned int lenght() {
		return heapCount;
	}

	T peekItem() {
		return heapArray[0];
	}

	T freezeItem(T item) {
		T temp = 0;

		if (heapCount > 0 && heapSize == heapCount) {
			temp = heapArray[heapCount - 1];

			heapArray[heapCount - 1] = item;

			heapSize--;

			heapCount--;

			freezedCount++;

			if (heapSize > 0) {
				temp = pushAndPopItem(temp);
			}
		} else
			throw new string("Could not freezeItem: Illegal Heap state");

		return temp;
	}

//	bool freezeItem(T item) {
//			bool temp = false;
//
//			if (heapSize > 0 && heapSize == (heapCount + 1)) {
//
//				heapArray[heapCount] = item;
//
//				heapSize--;
//
//				temp = true;
//			}
//
//			return temp;
//		}

	void unfreezeItems() {

		heapSize = heapMemory;

		heapCount = freezedCount;

		isHeap = false;

		freezedCount = 0;

		heapify();
	}

	unsigned int getFreezedItems() {
		return freezedCount;
	}

	void recoverFreezedItems() {

		heapArray = &heapArray[heapMemory - freezedCount];

		heapCount = heapSize = freezedCount;

		isHeap = false;

		freezedCount = 0;

		heapify();

	}

};

#endif
